﻿#pragma once
#include<vector>
/*闭散列结构的哈希表*/namespace CLOSE_HASH
{ 
	/*枚举表示-节点元素状态*/
	enum State
	{
		EMPTY,
		EXIST,
		DELETE,
	};

	/*数据格式-哈希表存储的节点元素*/
	template<class T>
	struct HashData
	{
		T _data;
		State _state;
	};

	/*哈希表（闭散列）*/
	template<class K,class T,class KOfT>
	class HashTable
	{
		typedef HashData<T> HashData;
	public:
		/*哈希表-成员函数-元素插入*/
		bool Insert(const T& d)
		{
			KOfT koft;
			size_t sz = _tables.size();
			/*1.判断负载因子（=数据/表的大小）*/
			/*二次探测负载因子*/if (sz == 0 || _num * 10 / sz >= 5)
			///*线性探测负载因子*/if (sz == 0 || _num * 10 / sz >= 7)
			{
				//增容（空间开二倍，旧表重新映射新表，释放旧表空间）
				/*a.原始写法*/
				/*size_t newsize = sz == 0 ? 10 : 2 * sz;
				vector<HashData> newtables;
				newtables.resize(newsize);
				for (size_t i = 0;i < sz;++i)
				{
					if (_tables[i]._state == EXIST)
					{
						size_t newindex = koft(_tables[i]._data) % newtables.size();
						while (newtables[newindex]._state == EXIST)
						{
							++newindex;
							if (newindex == newtables.size())
							{
								newindex = 0;
							}
						}
						newtables[newindex] = _tables[i];
					}
				}
				_tables.swap(newtables);*/
			
				/*b.复用写法*/
				HashTable<K,T,KOfT> newht;
				size_t newsize=sz == 0 ? 10 : 2 * sz;
				newht._tables.resize(newsize);
				for (size_t i = 0;i < sz;++i)
				{
					if (_tables[i]._state == EXIST)
					{
						newht.Insert(_tables[i]._data);
					}
				}
				_tables.swap(newht._tables);
			}
			/*2.计算映射位置*/

			/*a.线性探测*/
			/*size_t index = koft(d) % _tables.size();
			while (_tables[index]._state == EXIST)
			{
				if (koft(_tables[index]._data)== koft(d))
				{
					return false;
				}
				++index;
				if (index == _tables.size())
				{
					index = 0;
				}
			}*/

			/*b.二次探测*/
			size_t index_0 = koft(d) % _tables.size();
			size_t index = index_0, i = 1;
			while (_tables[index]._state == EXIST)
			{
				if (koft(_tables[index]._data) == koft(d))
				{
					return false;
				}
				index=(index_0+i*i)% (_tables.size());
				++i;
			}
			/*3.插入*/
			_tables[index]._data = d;
			_tables[index]._state = EXIST;
			_num++;
			return true;
		}

		/*哈希表-成员函数-元素查找*/
		HashData* Find(const T& key)
		{
			KOfT koft;
			/*1.计算位置*/
			/*a.线性探测*/
			/*size_t index = koft(key) % _tables.size();
			while (_tables[index]._state != EMPTY)
			{
				if (koft(_tables[index]._data) == koft(key))
				{
					if (_tables[index]._state == EXIST)
					{
						return &_tables[index];
					}
					else if (_tables[index]._state == DELETE)
						return nullptr;     
				}
				++index;
				if (index == _tables.size())
				{
					index = 0;
				}
			}*/

			/*b.二次探测*/
			size_t index_0 = koft(key) % _tables.size();
			size_t index = index_0, i = 1;
			/*2.查找元素*/
			while (_tables[index]._state == EXIST)
			{
				if (koft(_tables[index]._data) == koft(key))
				{
					if (_tables[index]._state == EXIST)
					{
						return &_tables[index];
					}
					else if (_tables[index]._state == DELETE)
						return nullptr;
				}
				index = (index_0 + i * i) % (_tables.size());
				++i;
			}
			return nullptr;
		}

		/*哈希表-成员函数-元素删除*/
		bool Erase(const T& key)
		{
			/*1.查找元素*/
			HashData* ret = Find(key);
			/*2.执行删除*/
			if (ret)
			{
				ret->_state = DELETE;
				--_num;
				return true;
			}
			else
			{
				return false;
			}
		}

	private:
		/*哈希表-成员变量*/
		vector<HashData> _tables;//顺序表结构哈希映射表
		size_t _num = 0;         //已存储元素数量
	};


	/*仿函数-T值转化为Key*/
	template<class K>
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};

	/*测试用例*/void TestHashTable_Closed()
{
	cout << "****HashTable_Closed测试用例开始****" << endl;
	HashTable<int, int, SetKeyOfT<int>> ht;
	ht.Insert(12);
	ht.Insert(24);
	ht.Insert(15);
	ht.Insert(6);
	ht.Insert(18);
	ht.Insert(25);
	ht.Insert(22);
	ht.Insert(78);

	cout << "****HashTable_Closed测试用例结束****" << endl << endl;
}
}

/*开散列结构的哈希表*/namespace OPEN_HASH
{
	/*哈希桶节点*/
	template<class T>
	struct HashNode
	{
		HashNode(const T& data = T()) :_data(data), _next(nullptr)
		{ }
		T _data;
		HashNode<T>* _next;
	};


	/*前置声明哈希表-迭代器用*/
	template<class K, class T, class KOfT, class Hash>
	class HashTable;
	/*哈希表迭代器*/
	template<class K, class T, class KOfT,class Hash>
	struct __HashTableIterator
	{
		/*类型重定义-迭代器关联使用*/
		/*哈希表*/typedef HashTable<K, T, KOfT, Hash> HT;
		/*哈希表桶节点*/typedef HashNode<T> Node;
		/*迭代器*/typedef __HashTableIterator<K,T,KOfT, Hash> Self;
		
		/*迭代器成员*/
		/*哈希表当前映射节点地址*/HT* _pht;
		/*哈希表当前桶节点地址*/Node* _node;
		
		/*迭代器-成员函数-构造*/
		__HashTableIterator(Node* node,HT* pht) :_node(node),_pht(pht) {}
		/*迭代器-成员函数-解引用重载*/
		T& operator*()
		{
			return _node->_data;
		}

		/*迭代器-成员函数-结构体指针访问符重载*/
		T* operator->()
		{
			return &_node->_data;
		}

		/*迭代器-成员函数- ++重载*/
		Self operator++()
		{
			if (_node->_next)
				_node = _node->_next;
			else
			{
				KOfT koft;
				size_t i=_pht->HashFunc(koft(_node->_data))%_pht->_tables.size()+1;
				for (;i < _pht->_tables.size();++i)
				{
					if (_pht->_tables[i])
					{
						_node = _pht->_tables[i];
						return *this;
					}
				}
				_node = nullptr;
			}
			return *this;
		}

		/*迭代器-成员函数- 不等重载*/
		bool operator !=(const Self& s)
		{
			return _node != s._node; 
		}

		/*迭代器-成员函数- 相等重载*/
		bool operator ==(const Self& s)
		{
			return _node == s._node;

		}
	};

	/*仿函数-哈希表取计算值key*/
	template<class K>
	struct _Hash
	{
		/*仿函数*/
		const K& operator()(const K& key)
		{
			return key;
		}
	};
	/*哈希表取计算值key*//*特化string类型*/
	template<>
	struct _Hash<string>
	{
		/*仿函数*/
		size_t operator()(const string& key)
		{
			//采用BKDR Hash 算法
			size_t hash = 0;
			for (size_t i = 0;i < key.size();++i)
			{
				hash *= 131;
				hash += key[i];
			}
			return hash;
		}
	};

	/*哈希表（开散列）*/
	template<class K, class T, class KOfT,class Hash>
	class HashTable
	{
		typedef HashNode<T> Node;
	public:
		friend struct __HashTableIterator<K, T, KOfT, Hash>;

		typedef __HashTableIterator<K, T, KOfT, Hash> iterator;
		/*哈希表-成员函数-迭代器起点begin()*/
		iterator begin()
		{
			for (size_t i = 0;i < _tables.size(); ++i)
			{
				if (_tables[i])return iterator(_tables[i],this);
			}
			return end();
		}
		/*哈希表-成员函数-迭代器终点end()*/
		iterator end()
		{
			return iterator(nullptr, this);
		}

		/*哈希表-成员函数-析构*/
		~HashTable()
		{
			Clear();
		}

		/*哈希表-成员函数-析构-遍历清理桶节点内存空间*/
		void Clear()
		{
			for (size_t i = 0;i < _tables.size();++i)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		/*哈希表-哈希表取计算值key（函数封装）*/
		size_t HashFunc(const K& key)
		{
			Hash hash;
			return hash(key);
		}

		/*哈希表-插入元素*/
		pair<iterator, bool> Insert(const T& data)
		{
			KOfT koft;
			size_t sz = _tables.size();
			if (_tables.size() == _nums)
			{
				vector<Node*> newtables;
				size_t newsize = sz == 0 ? 10 : sz * 2;
				newtables.resize(newsize);
				for (size_t i = 0;i < sz;++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t newindex = HashFunc(koft(cur->_data)) % newtables.size();
						cur->_next = newtables[newindex];
						newtables[newindex] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}
			size_t index = HashFunc(koft(data)) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (koft(cur->_data) == koft(data))
				{
					return make_pair(iterator(cur,this), false);
				}
				else
				{
					cur = cur->_next;
				}
			}
			Node* newnode = new Node(data);
			newnode->_next = _tables[index];
			_tables[index]=newnode;
			_nums++;

			return make_pair(iterator(newnode,this), true);
		}

		/*哈希表-查找元素*/
		Node* Find(const K& key)
		{
			KOfT koft;
			size_t sz = _tables.size(); 
			size_t index = HashFunc(key) % sz;
			Node* cur = _tables[index];
			while (cur)
			{
				if(koft(cur->_data)==key)
				{
					return cur;
				}
				else
				{
					cur = cur->_next;
				}
			}
			return nullptr;
		}

		/*哈希表-删除元素*/
		bool Erase(const K& key)
		{
			KOfT koft;
			size_t sz = _tables.size();
			size_t index = HashFunc(key) % sz;
			Node* cur = _tables[index];
			Node* prev=nullptr;
			while (cur)
			{
				if (koft(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_tables[index] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
		}
	private:
		/*哈希表-成员变量*/
		vector<Node*>_tables;//顺序表结构哈希映射表
		size_t _nums=0;      //已存储元素数量
	};

	/*哈希表-T值转换为有效K(测试用例用)*/
	template<class K>
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};

	/*测试用例*/void TestHashTable_Open1()
	{
		cout << "****HashTable_Open1测试用例开始****" << endl;
		HashTable<int, int, SetKeyOfT<int>, _Hash<int>> ht;
		ht.Insert(12);
		ht.Insert(24);
		ht.Insert(15);
		ht.Insert(6);
		ht.Insert(18);
		ht.Insert(25);
		ht.Insert(22);
		ht.Insert(78);

		cout << "****HashTable_Open1测试用例结束****" << endl;
	}

	/*测试用例*/void TestHashTable_Open2()
	{
		cout << "****HashTable_Open2测试用例开始****" << endl;
		//HashTable<string, string, SetKeyOfT<string>,_HashString> ht;//在计算映射地址时需要一个整形结果，而字符串类型不支持直接计算
		HashTable<string, string, SetKeyOfT<string> , _Hash<string>> ht;
		ht.Insert("use");
		ht.Insert("line");
		ht.Insert("sort");

		cout << "****HashTable_Open2测试用例结束****" << endl;
	}
}